package 中等.其他;

/**
 * 我们对 0 到 255 之间的整数进行采样，并将结果存储在数组 count 中：count[k] 就是整数 k 在样本中出现的次数。
 * 计算以下统计数据:
 * minimum ：样本中的最小元素。
 * maximum ：样品中的最大元素。
 * mean ：样本的平均值，计算为所有元素的总和除以元素总数。
 * median ：
 * 如果样本的元素个数是奇数，那么一旦样本排序后，中位数 median 就是中间的元素。
 * 如果样本中有偶数个元素，那么中位数median 就是样本排序后中间两个元素的平均值。
 * mode ：样本中出现次数最多的数字。保众数是 唯一 的。
 * 以浮点数数组的形式返回样本的统计信息 [minimum, maximum, mean, median, mode] 。与真实答案误差在 10-5 内的答案都可以通过。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/statistics-from-a-large-sample
 */
public class 大样本统计_1093 {

    public static void main(String[] args) {


    }

    /**
     * 模拟+两次遍历
     *
     * @param count
     * @return
     */
    public static double[] sampleStats(int[] count) {
        double[] ans = new double[5];
        ans[0] = 256;
        double sum = 0, cnt = 0;
        for (int k = 0; k < count.length; k++) {
            if (count[k] > 0) {
                ans[0] = Math.min(ans[0], k);
                ans[1] = Math.max(ans[1], k);
            }

            if (count[k] > count[(int) ans[4]]) {
                ans[4] = k;
            }

            sum += k * (double) count[k];
            cnt += count[k];
        }
        ans[2] = sum / cnt;

        if (cnt % 2 == 0) {
            int curCnt = 0;
            for (int k = 0; k < count.length; k++) {
                if (curCnt + count[k] > cnt / 2) {
                    ans[3] = k;
                    return ans;
                } else if (curCnt + count[k] == cnt / 2) {
                    for (int k2 = k + 1; k2 < count.length; k2++) {
                        if (count[k2] > 0) {
                            ans[3] = (k + k2) / 2D;
                            return ans;
                        }
                    }
                }
                curCnt += count[k];
            }
        } else {
            int curCnt = 0;
            for (int k = 0; k < count.length; k++) {
                if (curCnt + count[k] >= (cnt + 1) / 2) {
                    ans[3] = k;
                    return ans;
                }
                curCnt += count[k];
            }
        }
        return ans;
    }

    /**
     * 模拟+两次遍历
     */
    public double[] sampleStats2(int[] count) {
        double mininum = Double.MAX_VALUE, maxinum = Double.MIN_VALUE;
        int mode = 0;

        double sum = 0;
        long cnt = 0;
        for (int k = 0; k < count.length; k++) {
            if (count[k] > 0) {
                mininum = Math.min(mininum, k);
                maxinum = Math.max(maxinum, k);
            }
            sum += (double) count[k] * k;
            cnt += count[k];
            if (count[k] > count[mode]) {
                mode = k;
            }
        }

        double median = 0;
        // 如果总数量 cnt 为奇数，left == right 都是中间的那个数字索引
        // 如果为偶数，left，right 是中间的那两个数字索引
        long left = (cnt + 1) / 2, right = (cnt + 2) / 2;
        long curCnt = 0;
        for (int k = 0; k < count.length; k++) {
            // 加上当前的数字，left正好在其中，只会记录一次
            if (curCnt < left && curCnt + count[k] >= left) {
                median += k;
            }
            if (curCnt < right && curCnt + count[k] >= right) {
                median += k;
            }
            curCnt += count[k];
        }

        return new double[]{mininum, maxinum, sum / cnt, median / 2, mode};
    }

}
